# 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个
# 单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。 
# 
#  然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。 
# 
#  你需要计算完成所有任务所需要的 最短时间 。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：tasks = ["A","A","A","B","B","B"], n = 2
# 输出：8
# 解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
#      在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 
# 
#  示例 2： 
# 
#  
# 输入：tasks = ["A","A","A","B","B","B"], n = 0
# 输出：6
# 解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
# ["A","A","A","B","B","B"]
# ["A","B","A","B","A","B"]
# ["B","B","B","A","A","A"]
# ...
# 诸如此类
#  
# 
#  示例 3： 
# 
#  
# 输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
# 输出：16
# 解释：一种可能的解决方案是：
#      A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待
# 命) -> (待命) -> A
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= task.length <= 104 
#  tasks[i] 是大写英文字母 
#  n 的取值范围为 [0, 100] 
#  
#  Related Topics 贪心 数组 哈希表 计数 排序 堆（优先队列） 
#  👍 744 👎 0
import collections
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = collections.Counter(tasks)
        m = len(freq)
        next_valid = [1] * m
        rest = list(freq.values())

        time = 0
        for _ in range(len(tasks)):
            time += 1
            min_next_valid = min(next_valid[j] for j in range(m) if rest[j] > 0)
            time = max(time, min_next_valid)

            best = -1
            for j in range(m):
                if rest[j] > 0 and next_valid[j] <= time:
                    if best == -1 or rest[j] > rest[best]:
                        best = j
            next_valid[best] = time + n + 1
            rest[best] -= 1
        return time




# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 按照时间顺序分配任务
# 多种任务待执行, 选择剩余次数多的
# next_valid 最早可用时间
# rest 剩余执行次数
#     def leastInterval(self, tasks: List[str], n: int) -> int:
#         # 统计任务出现次数
#         freq = collections.Counter(tasks)
#
#         # 几种任务
#         m = len(freq)
#         # 每种任务下次可用时间
#         next_valid = [1] * m
#         rest = list(freq.values())
#
#         time = 0
#         # 遍历任务列表, 一遍循环为每次执行
#         for _ in range(len(tasks)):
#             # 确定时间
#             time += 1
#             # 有剩余次数, 查找最早可以执行的
#             min_next_valid = min(next_valid[j] for j in range(m) if rest[j] > 0)
#             # 跳过等待时间, 避免无效遍历
#             time = max(time, min_next_valid)
#
#             # 寻找当前可以执行, 且剩余次数最多的任务种类
#             best = -1
#             for j in range(m):
#                 if rest[j] >= 0 and next_valid[j] <= time:
#                     if best == -1 or rest[j] > rest[best]:
#                         best = j
#
#             # 下次执行时间: 当前 + 等待 + 1
#             # 减少剩余次数
#             next_valid[best] = time + n + 1
#             rest[best] -= 1
#         return time

if __name__ == '__main__':
    s = Solution()
    t1 = ["A", "A", "A", "B", "B", "B"]
    r1 = s.leastInterval(t1, 2)
    assert r1 == 8, r1
    t2 = ["A", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"]
    r2 = s.leastInterval(t2, 2)
    assert r2 == 16, r2
